import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author LKQ
 * @date 2022/3/5 14:02
 * @description
 */
public class Solution {
    int[][] rects;
    List<Integer> pSum = new ArrayList<>();
    int total = 0;
    Random rand= new Random();
    public Solution(int[][] re) {
        this.rects = re;
        for(int[] x: re) {
            //该矩形内整数点数目之和 加上之前的整数点，为递增序列
            total += (x[2] - x[0] + 1) * (x[3]-x[1] + 1);
            pSum.add(total);
        }
    }
    public int[] pick() {
        int targ = rand.nextInt(total);

        int lo = 0;
        int hi = rects.length - 1;
        // 二分查找 定位在那个矩形中
        while (lo != hi) {
            int mid = (lo + hi) / 2;
            if (targ >= pSum.get(mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        int[] x = rects[lo];
        int width = x[2] - x[0] + 1;
        int height = x[3] - x[1] + 1;
        // 当前矩形的整数点
        int base = pSum.get(lo) - width * height;
        return new int[]{x[0] + (targ - base) % width, x[1] + (targ - base) / width};
    }

}
